//
// Created by ASUS on 2023/12/13.
//
/*
 * 我们称一个分割整数数组的方案是 好的 ，当它满足：

数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。
示例 1：
输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
示例 2：
输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
示例 3：
输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。
提示：
3 <= nums.length <= 105
0 <= nums[i] <= 104
 */
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

const int mod=1e9+7;
int waysToSplit(vector<int>& nums) {
	int n=nums.size();
	vector<int> presum(n+1);
	presum[0]=0;
	for(int i=1;i<=n;i++) presum[i]=presum[i-1]+nums[i-1];
	long long ans=0;
	for(int i=1;i<n;i++){
		if(presum[i]*3>presum[n]) break;
		int l=i+1,r=n-1;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(presum[n] - presum[mid] >= presum[mid] - presum[i]) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		int ll = i + 1, rr = n - 1;
		while(ll <= rr) {
			int mid = (ll + rr) / 2;
			if(presum[mid] - presum[i] >= presum[i]) {
				rr = mid - 1;
			} else {
				ll = mid + 1;
			}
		}
		ans += r - ll + 1;
	}
	return ans%mod;
}
